home *** CD-ROM | disk | FTP | other *** search
/ Computer Select (Limited Edition) / Computer Select.iso / dobbs / v16n12 / memanage.asc < prev    next >
Encoding:
Text File  |  1991-11-11  |  6.8 KB  |  299 lines
  1. _A SIMPLE HANDLE-BASED MEMORY MANAGER_
  2. by David Betz
  3.  
  4. [LISTING ONE]
  5.  
  6. /* hmm.h - definitions for a simple handle based memory manager */
  7.  
  8. typedef char **HANDLE;
  9.  
  10. /* heap header structure */
  11. typedef struct heaphdr {
  12.     int hh_nhandles;    /* number of handles */
  13.     char *hh_next;  /* next free location */
  14.     char *hh_base;  /* base of heap memory */
  15.     char *hh_top;   /* top of heap memory */
  16.     HANDLE hh_handles;  /* base of handle array */
  17. } HEAPHDR;
  18.  
  19. HEAPHDR *NewHeap(int,int);
  20. void FreeHeap(HEAPHDR *);
  21. HANDLE HeapAlloc(HEAPHDR *,int);
  22. void HeapFree(HEAPHDR *,HANDLE);
  23.  
  24.  
  25.  
  26. [LISTING TWO]
  27.  
  28. /* hmm.c - a simple handle based memory manager  -- by David Betz */
  29.  
  30. #include <stdio.h>
  31. #include "hmm.h"
  32.  
  33. /* number of handles to add when expanding the handle table */
  34. #define HINC    32
  35.  
  36. /* block prefix structure */
  37. typedef struct blockpfx {
  38.     HANDLE bp_handle;   /* handle for this block */
  39. } BLOCKPFX;
  40.  
  41. /* block suffix structure */
  42. typedef struct blocksfx {
  43.     int bs_size;    /* size of block */
  44. } BLOCKSFX;
  45.  
  46. static HANDLE FindMemory(HEAPHDR *,HANDLE,int);
  47. static HANDLE NewHandle(HEAPHDR *);
  48. static HANDLE UnusedHandle(HEAPHDR *);
  49. static void ExpandHandleTable(HEAPHDR *,int);
  50. static void CompactHeap(HEAPHDR *);
  51.  
  52. /* NewHeap - allocate and initialize a new heap */
  53. HEAPHDR *NewHeap(nhandles,nbytes)
  54.   int nhandles;     /* initial number of handles */
  55.   int nbytes;       /* initial number of free bytes */
  56. {
  57.     char *malloc();
  58.     HEAPHDR *h;
  59.     int tsize;
  60.     HANDLE p;
  61.     tsize = nhandles * sizeof(char *);
  62.     if ((h = (HEAPHDR *)malloc(sizeof(HEAPHDR) + tsize + nbytes)) == NULL)
  63.     return (NULL);
  64.     h->hh_nhandles = nhandles;
  65.     h->hh_handles = p = (HANDLE)((char *)h + sizeof(HEAPHDR));
  66.     while (--nhandles >= 0) *p++ = NULL;
  67.     h->hh_base = (char *)h->hh_handles + tsize;
  68.     h->hh_top = h->hh_base + nbytes;
  69.     h->hh_next = h->hh_top;
  70.     return (h);
  71. }
  72.  
  73. /* FreeHeap - free a heap allocated by NewHeap() */
  74. void FreeHeap(h)
  75.   HEAPHDR *h;       /* heap to free */
  76. {
  77.     free(h);
  78. }
  79.  
  80. /* HeapAlloc - allocate a block of memory from the heap */
  81. HANDLE HeapAlloc(h,size)
  82.   HEAPHDR *h;       /* the heap */
  83.   int size;     /* size of block to allocate */
  84. {
  85.     HANDLE p;
  86.     if ((p = NewHandle(h)) == NULL)
  87.     return (NULL);
  88.     return (FindMemory(h,p,size));
  89. }
  90.  
  91. /* HeapFree - free a block of memory allocated by HeapAlloc() */
  92. void HeapFree(h,p)
  93.   HEAPHDR *h;       /* the heap */
  94.   HANDLE p;     /* the handle to free */
  95. {
  96.     BLOCKPFX *bp;
  97.     bp = (BLOCKPFX *)(*p - sizeof(BLOCKPFX));
  98.     bp->bp_handle = NULL;
  99.     *p = NULL;
  100. }
  101.  
  102. static HANDLE NewHandle(h)
  103.   HEAPHDR *h;       /* the heap */
  104. {
  105.     HANDLE p;
  106.     if ((p = UnusedHandle(h)) == NULL)
  107.     ExpandHandleTable(h,HINC);
  108.     return (UnusedHandle(h));
  109. }
  110.  
  111. static HANDLE UnusedHandle(h)
  112.   HEAPHDR *h;       /* the heap */
  113. {
  114.     HANDLE p;
  115.     int n;
  116.     for (p = h->hh_handles, n = h->hh_nhandles; --n >= 0; ++p)
  117.     if (*p == NULL)
  118.         return (p);
  119.     return (NULL);
  120. }
  121.  
  122. static void ExpandHandleTable(h,n)
  123.   HEAPHDR *h;       /* the heap */
  124.   int n;        /* number of handles to add */
  125. {
  126.     char *base;
  127.     HANDLE p;
  128.     CompactHeap(h);
  129.     base = h->hh_base + (n * sizeof(char *));
  130.     if (base <= h->hh_next) {
  131.     p = (HANDLE)h->hh_base;
  132.     h->hh_base = base;
  133.     h->hh_nhandles += n;
  134.     while (--n >= 0)
  135.         *p++ = NULL;
  136.     }
  137. }
  138.  
  139. static HANDLE FindMemory(h,p,size)
  140.   HEAPHDR *h;       /* the heap */
  141.   HANDLE p;     /* the handle to allocate space for */
  142.   int size;     /* size of block to allocate */
  143. {
  144.     BLOCKPFX *bp;
  145.     BLOCKSFX *bs;
  146.     int tsize;
  147.     char *d;
  148.     tsize = sizeof(BLOCKPFX) + size + sizeof(BLOCKSFX);
  149.     if ((d = h->hh_next - tsize) < h->hh_base) {
  150.     CompactHeap(h);
  151.     if ((d = h->hh_next - tsize) < h->hh_base)
  152.         return (NULL);
  153.     }
  154.     h->hh_next = d;
  155.     bp = (BLOCKPFX *)d;
  156.     bp->bp_handle = p;
  157.     d += sizeof(BLOCKPFX);
  158.     bs = (BLOCKSFX *)(d + size);
  159.     bs->bs_size = size;
  160.     *p = d;
  161.     return (p);
  162. }
  163.  
  164. static void CompactHeap(h)
  165.   HEAPHDR *h;       /* the heap */
  166. {
  167.     char *src,*dst;
  168.     BLOCKPFX *hp;
  169.     BLOCKSFX *hs;
  170.     src = dst = h->hh_top;
  171.     while (src > h->hh_next) {
  172.     hs = (BLOCKSFX *)(src - sizeof(BLOCKSFX));
  173.     hp = (BLOCKPFX *)((char *)hs - hs->bs_size - sizeof(BLOCKPFX));
  174.     if (hp->bp_handle) {
  175.         if (src == dst)
  176.         src = dst = (char *)hp;
  177.         else {
  178.         while (src > (char *)hp)
  179.             *--dst = *--src;
  180.         *hp->bp_handle = dst + sizeof(BLOCKPFX);
  181.         }
  182.     }
  183.     else
  184.         src = (char *)hp;
  185.     }
  186.     h->hh_next = dst;
  187. }
  188.  
  189.  
  190.  
  191. [LISTING THREE]
  192.  
  193.  
  194. OFILES=hmmtest.obj hmm.obj
  195.  
  196. hmmtest.exe:    $(OFILES)
  197.     cl $(OFILES)
  198.  
  199.  
  200.  
  201. [LISTING FOUR]
  202.  
  203. #include <stdio.h>
  204. #include "hmm.h"
  205.  
  206. HANDLE allocshow(int);
  207. void showheap(void);
  208. void pause(void);
  209.  
  210. #define HMAX    100
  211.  
  212. HEAPHDR *h;
  213. HANDLE handles[HMAX];
  214.  
  215. main()
  216. {
  217.     int i;
  218.  
  219.     /* allocate a heap */
  220.     h = NewHeap(16,4096);
  221.     showheap();
  222.     pause();
  223.  
  224.     /* allocate a bunch of blocks of memory from the heap */
  225.     printf("Allocating...\n");
  226.     for (i = 0; i < HMAX; ++i) {
  227.     printf("%2d: ",i);
  228.     handles[i] = allocshow(32);
  229.     sprintf(*handles[i],"%d",i);    /* put something in the block */
  230.     putchar('\n');
  231.     }
  232.  
  233.     /* show the state of the heap after the allocations */
  234.     showheap();
  235.     pause();
  236.  
  237.     /* free every other block (to test the compaction algorithm) */
  238.     printf("Deallocating...\n");
  239.     for (i = 0; i < HMAX; i += 2)
  240.     HeapFree(h,handles[i]);
  241.  
  242.     /* show the state of the heap after the deallocations */
  243.     showheap();
  244.     pause();
  245.  
  246.     /* now reallocate the blocks we freed (causes compaction) */
  247.     printf("Reallocating...\n");
  248.     for (i = 0; i < HMAX; i += 2) {
  249.     printf("%2d: ",i);
  250.     handles[i] = allocshow(32);
  251.     sprintf(*handles[i],"%d",i);
  252.     putchar('\n');
  253.     }
  254.  
  255.     /* show the state of the heap after the new allocations */
  256.     showheap();
  257.     pause();
  258.  
  259.     /* make sure all of the blocks contain what we expect */
  260.     printf("Checking...\n");
  261.     for (i = 0; i < HMAX; ++i) {
  262.     printf("%2d: %04x->%04x=",i,handles[i],*handles[i]);
  263.     printf("%s",*handles[i]);
  264.     if (atoi(*handles[i]) != i)
  265.         printf(" *** ERROR");
  266.     putchar('\n');
  267.     }
  268.  
  269.     /* free the heap and exit */
  270.     FreeHeap(h);
  271. }
  272.  
  273. HANDLE allocshow(size)
  274.   int size;
  275. {
  276.     HANDLE p;
  277.     if (p = HeapAlloc(h,size))
  278.     printf("%04x->%04x",p,*p);
  279.     return (p);
  280. }
  281.  
  282. void pause()
  283. {
  284.     while (getchar() != '\n')
  285.     ;
  286. }
  287.  
  288. void showheap()
  289. {
  290.     printf("nhandles: %d\n",h->hh_nhandles);
  291.     printf("handles:  %04x\n",h->hh_handles);
  292.     printf("base:     %04x\n",h->hh_base);
  293.     printf("next:     %04x\n",h->hh_next);
  294.     printf("top:      %04x\n",h->hh_top);
  295. }
  296.  
  297.  
  298.  
  299.